This invention relates to a method of and an apparatus for storing priority levels in a token-ring network system which permits intercommunication through a ring transmission link.
The token-ring network system has hitherto been known as one of schemes in which a plurality of originators can equally communicate with desired terminators through a common transmission link. Exemplified in FIG. 1 is a system configuration of a general token-ring network system. According to this architecture, four intercommunicative data processors 1A, 1B, C and 1D are accommodated in a transmission link 3 through four associated nodes 2A, 2B, 2C and 2D, and data can be transferred in a direction of arrows shown in FIG. 1 (counterclockwise). A token, a bit sequence of several bytes, for example three bytes, is passed from one node to another around the ring transmission link 3 to give permission to the receiving node to initiate a transmission (a right to transmission of data). Where a data processor (originator) is requesting a data transmission, this data processor acquires a right to transmission when a node associated therewith receives a token, and that node transmits a frame inclusive of the transmission data in place of the received token. When the transmitted frame has once been received by a node associated with a desired receiving data processor (terminator) and thereafter has taken a round on the transmission link 3 to reach the transmitting node associated with the originator, this originator node transmits a token in place of the received frame in order to give a right to transmission to another node. However, the data processor requesting the data transmission is not always permitted to transmit the data whenever the associated node receives the token, because a priority level is defined in data which is requested for transmission by any of the data processors. More specifically, when a node associated with a particular data processor requesting a data transmission receives a token under concurrence of a request by a different data processor for transmission of a data of a higher priority level than that of the data of the particular data processor, the node associated with the particular data processor transmits another token which gives a right to transmission to a node associated with the different data processor requesting the transmission of the higher priority level data.
FIG. 2a illustrates a format of a token 4 to be transferred on the transmission link 3 and FIG. 2b a format of a frame 5 also to be transferred on the link 3. Either of the token 4 and frame 5 contains a starting delimiter (SD) 6 in the header field and an ending delimiter (ED) 8 in the endmost field so that the node can recognize either of the token and frame in unit of packet. Thus, two kinds of packets are used in the system.
The token 4 additionally contains an access control field (AC) 7 which is interposed between the SD 6 and ED 8. The AC 7 exemplarily has one byte and includes, as detailed in FIG. 2a, a priority level sub-field (P) 71 to be written with a encoded value (three bits) of a current priority level (for example, the priority is graded by eight levels), a reservation (priority) level sub-field (R) 74 to be written with a encoded value (three bits) of a priority level of a data reserved for transmission, a token sub-field (T) 72 for indication as to whether a packet of interest is a token 4 or a frame 5 (for example, T="0" is used for indicating the token and T="1" for the frame), and a monitor count sub-field (MC) 73 to be written with a count value (one bit) indicative of the number (frequency) of circulation of the packet along the transmission link 3.
The frame 5 shown in FIG. 2b contains, like the token 4, an SD 6, an AC 7 (having a token sub-field of T="1" as mentioned previously), and an ED 8, with addition of a data field 9 to be written with a transmission data and a frame check field 10 for detection of errors in the transmission data. Although not illustrated in FIG. 2b the data field 9 has, at predetermined locations, sub-fields to be written with codes indicative of an originator and a terminator of the data, respectively.
The operation of the known token-ring network system will now be described with reference to FIG. 1.
In the configuration of FIG. 1, it is indicated by TK (0, 0) with .circle.1 that a taken having a current priority level sub-field (P) 71 indicative of "0 (zero)" and a reservation level sub-field (R) 74 indicative of "0 (zero)" has initially been issued from the node 2A. Namely, in FIG. 1, numerals encircled by a symbol " .circle. " indicate sequence of transfer of tokens or frames, and TK with a parenthesis filled with the initial numeral indicative of a value of P and the following numeral indicative of a value of R indicates a token. In connection with the numerals, the larger the numerical value, the higher the priority level is. It is now assumed that upon the issuance of the token TK (0, 0) indicated by .circle.1 , the nodes 2B, 2C and 2D are requesting data transmissions, the priority levels, Pm, of transmission data of the nodes 2B and 2C are all zero and only the node 2D has the priority level Pm which is 5, and that the transmission data from each node are all directed to the node 2A standing for a terminator. The node 2B receives the token TK (0, 0) from the node 2A and compares the value of P in this token with the priority level of a data of its own to be transmitted. If the value of P is equal to or smaller than the priority level of the transmission data of its own, the node 2B acquires a right to transmission and transmits a frame inclusive of the transmission data. Since, in this example, the value of P in the token TK (0, 0) from the node 2A is 0 (zero) and the priority level of the data requested for transmission by the node 2B is also 0 (zero) equalling the value of P, the node 2B acquires a right to transmission and transmits a frame FR.sub.B (0, 0) indicated by .circle.2 in place of the token TK (0, 0). The symbol FR.sub.B referred to here indicates a frame issued from the node 2B, with its parenthesis filled, like the parenthesis of the token, with the initial numeral indicative of a value of P and the following numeral indicative of a value of R in the access control field 7 of the frame format.
The frame FR.sub.B (0, 0) indicated by .circle.2 from the node 2B is received by the node 2C. If the value of reservation level R in the frame FR.sub.B (0, 0) is larger than the priority level of the data of its own to be transmitted, the node 2C rewrites the value of R in the frame FR.sub.B (0, 0) into a new one. In this example, since the priority level of the data which the node 2C intends to transmit is zero equalling the value of R in the frame FR.sub.B (0, 0) the node 2C transmits the frame FR.sub.B (0, 0) received from the node 2B without rewriting it.
The node 2D receives the frame FR.sub.B (0, 0) from the node 2C and compares the priority level (Pm=5) of the data of its own to be transmitted with the value of R in the frame FR.sub.B that is, zero. Since in this example the priority level of the data which the node 2D intends to transmit is larger, the node 2D rewrites the value of reservation level R in the frame FR.sub.B (0, 0) to 5 which is the priority level of the data of its own to be transmitted, thereby transmitting a frame FR.sub.B (0, 5) indicated by .circle.3 .
The node 2A receives from the node 2B the transmission data contained in the frame FR.sub.B (0, 5). There is no data that the node 2A intends to transmit and hence the node 2A, after reception of the transmission data from the node 2B, returns to the node 2B the frame FB.sub.B (0, 5) as it is.
When receiving the frame FR.sub.B (0, 5) indicated by .circle.4 , the node 2B recognizes that the data transmitted from its own node has taken a round on the transmission link 3, that is, the data transmission of its own has been completed. The node 2B then issues a token in place of the frame FR.sub.B (0, 5). Concurrently, the node 2B examines the value of reservation level R to recognize that there is a node which intends to transmit the data having the priority level measuring 5. Then, for the sake of urgently transferring the right to transmission to the node requesting the transmission of the data having the priority level "5", that is, to the node 2D, the node 2B transmits a token TK (5, 0) indicated by .circle.5 . It should therefore be noted that the node 2B has rewritten the value "0" of current priority level in the token TK (0, 0), indicated by .circle.1 received previously from the node 2A, into 5 in the token TK (5, 0) indicated .circle.5 . Following the rewriting to the priority level in the token, the node 2B stores both of the current priority level i.e., 5 and the previous priority level i.e., 0.
Since the priority level P i.e., 5 in the token TK (5, 0) from the node 2B is higher than the priority level i.e., 0 of the data the node 2C intends to transmit, the node 2C is not permitted to transmit the data of its own and transfers to the node 2D the token TK (5, 0) as it is.
Receiving the token TK (5, 0), the node 2D recognizes that the value of priority level P in the token equals the priority level of the data of its own to be transmitted, acquiring a right to transmission and transmits a frame FR.sub.D (5, 0) indicated by .circle.6 in place of the token TK (5, 0). The symbol FR.sub.D referred to here indicates a frame issued from the node 2D.
Gathering from the operation of each node set forth so far, it will be understood easily that the frame FR.sub.D (5, 0) transmitted from the node 2D will remain unchanged so as to take a round on the transmission link 3, thereby returning, as designated at the frame FR.sub.D (5, 0) indicated by .circle.7 , to the node 2D. By receiving the frame FR.sub.D (5, 0), the node 2D recognizes that the transmission of the data of its own has been completed. Accordingly, the node 2D transmits a token which substitutes for the frame FR.sub.d (5, 0) and which is TK (5, 0) indicated by .circle.8 . The value of priority level P in the TK (5, 0) indicated by .circle.8 is set to be 5 because this token should urgently be transferred to the node which has previously raised the priority level in the token to 5 (in this example, the node 2B). If the node 2D transmits a token TK (0, 0), a node (in this example, node 2A) next to the node transmitting the data of the high priority level will always have the advantage of data transmission and equality in communication by the nodes on the transmission link 3 will be impaired.
When receiving the token TK (5, 0) issued from the node 2D and transferred via the node 2A, the node 2B compares the value "5" of priority level P in that token TK (5, 0) with the priority level in the token which has previously been rewritten and stored in the node 2B. Coincidence in this comparison means that the node 2B is identified as the node which has raised the priority level in the current token TK (5, 0) and therefore, it is necessary for the node 2B to lower the priority level in this token TK (5, 0) to the priority level which has measured prior to rewriting and stored in the node 2B. This allows position and state of that token to be reset to those which have measured prior to the occurrence of the request by the node 2D for the transmission of the higher priority level data, thereby maintaining equality in communication by the node in the transmission link 3. Consequently, the node 2B transmits a token TK (0, 0) indicated by .circle.9 .
As will be seen from the above, when each node has raised by itself the priority level in the token, each node must store a pair of values of un-rewritten and rewritten priority levels. In addition, there is a possibility that each node sequentially performs operations to raise the priority level, without interrupted by lowering the priority level.
Conventionally, each node has a first-in last-out (FILO or stack) register of relatively large memory capacity as a means for storing values of the paired priority levels, requiring a complicated circuit adapted to control write/read operations of the values. Taking the above example, for instance, the 8 priority levels ranging level "0" to level "7" are set and therefore, when a particular node performs the maximum number of operations to raise the priority level, four operations for raising priority level "0" to level "1", level "2" to level "3", level "4" to level "5" and level "6" to level "7" are carried out by the particular node in the order mentioned. Accordingly, the FILO (stack) register of each node has a nesting of four levels. It follows therefore that in the above example, memory capacity of the FILO register in each node is required to be EQU 3 (bits).times.2.times.4 (nesting levels)=24 bits.
Prior to describing a conventional method of storing priority levels, details of the respective nodes shown in FIG. 1 will first be described with reference to FIG. 3. Although the node 2B is exemplarily broken down in FIG. 3, it should be noted that each of the other nodes 2A, 2C and 2D has the same internal circuit construction. A frame or token outputted from the node 2A is passed through the transmission link 3 so as to be fed to a bit rewrite circuit 32 and a shift register 33 via a receiver 30. The shift register 33 converts the frame or taken into a parallel receiving data which in turn is supplied to a frame/token detector circuit 34 and a receiving data first-in first-out (FIFO) register 38. Thus, only the received data is sent to the data processor 1B via a data bus. The bit rewrite circuit 32 is responsive to a rewrite data from the frame/token detector circuit 34 to rewrite the value of reservation level in the access control field 7 of the frame or token. Values of priority level sub-field P and reservation level sub-field R in the access control field 7 of the frame or token are sent from the frame/token detector circuit 34 to a priority level storing (and controlling) circuit 35. Based on the received values, the circuit 35 controls a frame or token to be transmitted.
For transmission, the priority level storing (and controlling) circuit 35 supplies to a token/frame generator circuit 36 values written in the access control field 7 of the frame or token to be transmitted. A transmission data from the data processor 1B is sent via the data bus to a transmitting data first-in first-out register 39 and fed, as a parallel transmission data, to a shift register 37. A transmission data from the token/frame generator circuit 36 is also fed, as a parallel transmission data, to the shift register 37. The transmission data from the shift register 37 is sent via a driver 31 to the transmission link 3 and transmitted to the node 2C.
The schematic construction of the conventional priority level storing circuit 35 shown in FIG. 3 is illustrated in FIG. 4. Referring to FIG. 4, the priority level storing circuit 35 comprises a frame priority level register 14 for storing a value Pr of current priority level in the access control field 7 of a frame, a reservation level register 15 for storing a value Rr of the reservation level, a priority level controller 13 for judging the relation between magnitudes of the priority levels, an FILO controller 16, 16', a first priority level FILO register 17, a second priority level FILO register 18, a first priority level read register 19, and a second priority level read register 20.
The conventional priority level storing circuit 35 schematically shown in FIG. 4 is further detailed in FIG. 5. The operation of this circuit 35 will now be described with reference to FIG. 5.
Firstly, the operation will be explained by referring, as an example, to the reception by the node 2B of the frame FR.sub.B (0, 5) indicated by .circle.4 , shown in FIG. 1, and the transmission by the node 2B of the token TK (5, 0) indicated by .circle.5 , also shown in FIG. 1. When the node 2B receives the frame FR.sub.B (0, 5), a binary value "000" (or decimal "0") is loaded on the register 14 of FIG. 5 and a binary value "101" (or decimal "5") is loaded on the register 15 of FIG. 5. A comparator 44 compares contents Pr and Rr of the registers 14 and 15 and supplies a signal indicative of Pr&lt;Rr to a priority level judging circuit 47. On the other hand, the registers 19 and 20 have already been loaded with contents Sx and Sr of "000", respectively, because in this example the node 2B has the priority level Pm which is "0". Consequently, a comparator 43 supplies a signal indicative of Pr=Sx and a comparator 45 supplies a signal indicative of Rr&gt;Sr, to the priority level judging circuit 47. An input/output control circuit 41 is so configured as to write the value of priority level from a selector circuit 46 to the FILO register 18 and the same value also to the register 20, ensuring that the content of the register 20 coincides with the content at the top level of the FILO register 18. In exact similarity, the content of the register 19 coincides with the content at the top level of the FILO register 17. The priority level judging circuit 47 obtains conditions Pr&lt;Rr and Pr&gt;Sx from a combination of the signals delivered out of the comparators 43, 44 and 45. Under the above conditions, the circuit 47 issues a control signal to the selector circuit 46 so as to cause the same to connect the content Pr of the register 14 to the input/output control circuit 41 and connect the content Rr of the register 15 to an input/output control circuit 42. At the same time, the priority level judging circuit 47 sends write signals to control circuits 16 and 16' in order that the input/output control circuits 41 and 42 can write the values from the selector circuit 46 into the associated FILO registers 18 and 17. Consequently, as described previously, the content Rr (in this example, "101") of the register 15 is loaded on the register 19 and the content Pr (in this example, "000") of the register 14 is loaded on the register 20.
Next, the operation of the FIG. 5 circuit will be described by referring, as an example, to the node 2B receiving the token TK (5, 0) indicated .circle.8 and then transmitting the token TK (0, 0) indicated by .circle.9 in FIG. 1. When the node 2B receives the token TK (5, 0), a binary value "101" is loaded on the register 14 of FIG. 5 and a binary value "000" on the register 15. As described previously, since the content Sx of the register 19 is "101" and the content Sr of the register 20 is "000", the comparator 43 supplies a signal indicative of Pr=Sx and the comparator 45 supplies a signal indicative of Rr.ltoreq.Sr, to the priority level judging circuit 47. The priority level judging circuit 47 thus obtaining conditions Rr.ltoreq.Sr and Pr=Sx supplies read signals to the control circuits 16 and 16', causing the associated FILO (stack) registers 17 and 18 to pop up. The input/output control circuits 41 and 42, on the other hand, respond to switching signals from the control circuits 16' and 16 to change their input/output modes, so that the contents at the second level of the FILO (stack) registers 18 and 17, which have been popped up and read out, are written into the associated registers 20 and 19. In this case, both the registers 19 and 20 are written with "000". Concurrently, the priority level judging circuit 47 controls the selector circuit 46 such that the contents of the registers 19 and 20 are sequentially switched to provide a data which is necessary for generation of the token TK (0, 0) and sent to the token/frame generator circuit 36 (FIG. 3). To add, when the reservation level loaded on the register 15 is smaller than the priority level loaded on the register 14, the priority level storing circuit 35 is not brought into any operation.
As described above, the conventional priority level storing circuit 35 requires such sophisticated operations as stacking operations for the FILO registers 17 and 18 and switching operations for the input/output control circuits 41 and 42, resulting in the complicated construction. Moreover, the memory capacity of the FILO registers 17 and 18 must in all be 24 bits.
The token-ring network system is disclosed in "A Local Communications Network Based on Interconnected Token-Access Rings: A tutorial" by Norman C. Strole, IBM J. RES. DEVELOP., Vol. 27, No. 5, pp 481-496, September, 1983 and "Draft IEEE Standard 802.5, Token Ring Access Method and Physical Layer Specifications", pp 17-19, June 10, 1983.